# 几种硬币任意数量凑成指定金额的钱，什么时候使用的硬币最少
# 状态：即在变化的量，这里只有amount在变化
# 选择：导致状态发生变化的行为，这里是选硬币
# base case: 基线

# 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
#
# 按上面的套路走，最后的结果就可以套这个框架：
#
# # 初始化 base case
# dp[0][0][...] = base
# # 进行状态转移
# for 状态1 in 状态1的所有取值：
#     for 状态2 in 状态2的所有取值：
#         for ...
#             dp[状态1][状态2][...] = 求最值(选择1，选择2...)
import sys

# 思路就是，将amount打散成一枚枚的硬币，每次取走一个，然后比较，取到amount为0说明这次取值成功，取到负数说明无法匹配需要继续遍历，与fib类似: 如果amount过大会导致栈深度超出溢出
Memo = dict()


# 自上而下递归+备忘录方法
def coins_count(coin_types, amount):
    # 增加备忘录，用空间换取计算时间
    if amount in Memo:
        return Memo[amount]
    if amount == 0:
        return 0
    # 跳出条件，如果小于0说明超过了值了
    if amount < 0:
        return -1
    res = sys.maxsize
    for coin in coin_types:
        sub_problem = coins_count(coin_types, amount - coin)
        if sub_problem == -1:
            continue
        res = min(res, sub_problem + 1)
    Memo[amount] = res if res != sys.maxsize else -1
    return Memo[amount]


# 自下而上遍历方法，逐个从0 1 2 3 4 5 6 依次比较得到到达对应数值的最少coin数量，然后使用后续的相加
def coins_count_for(coin_types, amount):
    # 初始化amount+1大小字典
    amount_map = {}
    for i in range(amount + 2):
        amount_map[i] = amount + 1
    # base 关键金额为0的时候，数量为0，金额为1的时候数量为0+1，数量为2时，比较到达0时的最小数，有点像步长 ，还是有点费解！！！
    amount_map[0] = 0
    for k, v in amount_map.items():
        for coin in coin_types:
            if amount - coin < 0:
                continue
            amount_map[k] = min(amount_map[k], 1 + amount_map[amount - coin])
    return -1 if amount_map[amount] == amount + 1 else amount_map[amount]


if __name__ == '__main__':
    print(coins_count([1, 5, 10], 10))
    print(coins_count_for([1, 5, 10], 10))
